
def F(n):
    n2 = int(n * 0.5)
    primeList = [];
    primeDict = {}
    isPrime = [1 for i in xrange(n + 1)]
    for i in xrange(2, n + 1):
        if isPrime[i]:
            primeList.append(i)
            primeDict[i] = True
            for j in xrange(i + i, n + 1, i):
                isPrime[j] = 0
    # done prime
    def coprime(x, factx, m):
        length = len(factx)
        cop = 0
        for bit in xrange(1, 1 << length):
            count = 0
            bb = bit
            while bb:
                if bb & 1:
                    count += 1
                bb >>= 1
            prod = 1
            for i in xrange(length):
                if (1 << i) & bit:
                    prod *= factx[i]
            countProd = m / prod
            if count % 2 == 1:
                cop += countProd
            else:
                cop -= countProd
        return cop

    n2 = int(n ** 0.5)
    for d in xrange(1, n2 + 1):
        d2 = int(d ** 0.5)
        for div in xrange(1, d2 + 1):
            if d % div == 0:
                # d / div = dd, dd is integer
                x = d / div
                factx = []
                xx = x
                for prime in primeList:
                    if x


N = 10 ** 3
F(N)

def F2(n):
    for i in xrange(1, n + 1):
        ans += f(i)
    return ans

def f(n):
    n2 = int(n ** 0.5)
    ans = 0
    for i in xrange(1, n2 + 1):
        if n % i == 0:
            ni = n / i
            gd = gcd(i, ni)
            ans += gd
            if i != ni:
                ans += gd
    return ans

